#! /usr/bin/python

import math
import time

now = time.time()

def isPrime(n):
    if n == 2 or n==3 or n==5 or n==7: return True
    if n%2 == 0 or n%3==0 or n==1: return False
    for i in range(5, int(math.sqrt(n) + 1), 6):
	if n%i == 0 or n%(i+2) == 0: return False
    return True

def gcd(a, b):
    if b == 0: return a
    return gcd (b, a%b)

nlist = set([4])
primes = [2]

for i in range(3, 10**4, 2):
    if isPrime(i): 
	primes.append(i)
	nlist.add(i**2)

for i in range(len(primes)):
    for j in (i+1, len(primes)):
	index = i*j
        if index >= 10**8: break
	nlist.add(index)

nlist2 = set()
for i in range(4, 10**5):
    for p in primes:
	if i == p: break
	index = i*p
	if index >= 10**8: break
	if nlist[index] != 0: continue
	if gcd(i, p) == 1: 
	   nlist[index] = nlist[i] * nlist[p]
	else: nlist[index] = -1


print nlist.count(3) + nlist.count(4)
print time.time() - now
